package backspaceCompare;

import java.util.Stack;

public class Solution {
    public boolean backspaceCompare(String s, String t) {
        //
//        Stack<Character> stack1 = get(s);
//        Stack<Character> stack2 = get(t);
//        if(stack1.size()!=stack2.size()) return false;
//        while (!stack1.isEmpty()) {
//            if(stack1.pop()!=stack2.pop())return false;
//        }
//        return true;

        // 双指针
        // 每个字母是否被删除 只取决于它后面的'#'
        // 因此 我们可以倒叙遍历
        int n = s.length(),m = t.length();
        int i = n-1,j = m-1;
        int skipS = 0,skipT = 0;
        while (i>=0||j>=0) {
            // 每个字符是否被删除 只取决于它后面的字符
            while (i>=0) {
                if(s.charAt(i) == '#') {
                    skipS++;
                    i--;
                } else if (skipS>0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }
            while (j>=0) {
                if(t.charAt(j) == '#') {
                    skipT++;
                    j--;
                } else if (skipT>0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }
            if(i>=0&&j>=0) {
                if(s.charAt(i)!=t.charAt(j)) {
                    return false;
                }
            } else {
                if(i>=0||j>=0) {
                    return false;
                }
            }
            i--;
            j--;
        }
        return true;
    }
//    private Stack<Character> get (String s) {
//        Stack<Character> stack1 = new Stack<>();
//        for (int i = 0; i < s.length(); i++) {
//            if(s.charAt(i) == '#') {
//                // 退格
//                if(!stack1.isEmpty())
//                    stack1.pop();
//            } else {
//                stack1.add(s.charAt(i));
//            }
//        }
//        return stack1;
//    }
}
